#include "p4.h"
using namespace std;
string file;
ofstream output;
bool tiempo = false;




string get_file_contents(const char *filename){
	ifstream in(filename, std::ios::in | std::ios::binary);
	if (in){
		string contents;
		in.seekg(0, std::ios::end);
		contents.resize(in.tellg());
		in.seekg(0, std::ios::beg);
		in.read(&contents[0], contents.size());
		in.close();
		return(contents);
	}
	perror("Error:");
	return 0;
}

int main(int argc, char *argv[]) {

	if(argc ==1){
		cout << "Usando p4.in y p4.out" << endl;
		file = get_file_contents("p4.in");
		output.open("p4.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==3){
		cout << "Usando " << argv[1] << " y " << argv[2] << endl;
		file = get_file_contents(argv[1]);
		output.open(argv[2]);
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else if(argc ==2 && string (argv[1]) == "time"){
		cout << "Calculando tiempos usando p4.in y p4.out con " << ITER << " iteraciones" << endl;
		tiempo = true;
		file = get_file_contents("p4.in");
		output.open("p4.out");
		if(output.fail()){
			cerr << "Error al abrir archivo de salida" << endl;
		}
	}

	else{
		cout << "Modo de uso: \"p4 input output\" o \"p4 time\" para benchmark" << endl;
		return 0;
    }

	istringstream input;
	input.str(file);

	int k; //k piezas

	string l1;
	getline(input,l1);
	istringstream ssl1(l1);
/*----------------------------------------------------------------------------*/
	/*ARMO EL TABLERO */
/*----------------------------------------------------------------------------*/

	tablero tab;
	ssl1 >> tab.altura; //guardo n filas = altura
	ssl1 >> tab.base; //guardo m columnas = base
	ssl1 >> k;  //guardo k piezas
	tab.cantLibres = tab.base * tab.altura;
	int cant = k; // me guardo el k

    vector<int > v1;
	string l2;
	int x;
	int negrosTablero = 0;
	for(int i = 0 ; i<tab.altura && !input.eof();i++){
				getline(input,l2);
				istringstream ssl2(l2);
                v1.erase(v1.begin(),v1.end());
				for(int l = 0;l<tab.base;l++){

					ssl2 >> x; //agarro el elemento
					v1.push_back(x); // lo agrego al fondo del vector de puntos (0 y 1)
					//puntosTab.push_back(x);
                    if(x == 0){
                        negrosTablero++;
                    }

				}
				tab.colores.push_back(v1);
			}

    tab.cantNegras = negrosTablero;
/*----------------------------------------------------------------------------*/
    /*ARMO EL FICHERO CON LO QUE VIENE DEL ARCHIVO*/
/*----------------------------------------------------------------------------*/
	vector<ficha > fichero; // arreglo de fichas
	int negrosFicha ;
	int id = 0;
	while(cant>0 && !input.eof() ){
		// primera linea tiene tamaño n. m
		getline(input,l2);
		istringstream ssl2(l2);
		ficha f1;
		f1.rotacion = 0;
		ssl2 >> f1.altura;
		ssl2 >> f1.base;
		negrosFicha = 0;


		for(int p = 0; p < f1.altura;p++){
		getline(input,l2);
		istringstream ssl2(l2);
                v1.erase(v1.begin(),v1.end());
				for(int o = 0;o < f1.base ; o++){
                     ssl2 >> x;
				     v1.push_back(x);
                      if(x == 0){negrosFicha++;}
		}
        f1.puntos.push_back(v1);


	}
	f1.id = id;
	f1.cantNegras = negrosFicha;
    fichero.push_back(f1);
	cant--;
	id++;
    }


/*
    ofstream myfile;
  myfile.open ("example.txt");

  for(int i = 0 ; i < tab.altura;i++){
    for(int j = 0; j<tab.base ;j++){
        myfile << tab.colores[i][j] << " " ;
    }
    myfile<< endl;
  }
myfile<< "\n "<< endl;
  ficha f ;
  f.base = tab.base;
  f.altura = tab.altura;
  vector<vector<int> > res;
   for(int i = 0 ; i < tab.altura;i++){
       v1.erase(v1.begin(),v1.end());
    for(int j = 0; j<tab.base ;j++){
       v1.push_back(tab.colores[i][j]);
    }
    res.push_back(v1);
  }
    f.puntos = res;

  myfile<< "\n "<< endl;
      rotar(f);
  for(int i = 0 ; i < f.altura;i++){
    for(int j = 0; j<f.base ;j++){
        myfile << f.puntos[i][j] << " " ;
    }
    myfile<<  endl;
  }

  myfile.close();
  return 0;*/
		/*if(tiempo){
			uint64_t t;
			uint64_t res = 0;
			for(int i=0;i<ITER;i++){
//				t=rdtsc();
				resolver(k,base,altura,vx,vy,puntos);
//				t = rdtsc() -t;
				res = res + t;
			}
		res = res/ITER;
		cout << "For k= " << k << " process took: "<< res << " ticks" << endl;
		}
*/
	vector<posiciones > sol ;
	bool res = resolver(tab,k,fichero,sol);
    if(res){
        salida(output,sol);
	}else{
	output << 0;
        cout << "no tiene solucion" <<endl;
    }



	output.close();
//borro todo

//fin borrar;
	return 0;
}


bool resolver(tablero& tab,int& k,  vector<ficha >& fichero,vector<posiciones> & pos ){
	int x = 0;
	int y = 0;
    vector<int> v1;
    for(int i = 0; i < tab.altura; i++){
        v1.erase(v1.begin(),v1.end());
        for(int j = 0; j<tab.base;j++){
            v1.push_back(0);
        }
        tab.usadas.push_back(v1);
    }

	bool res = backtrack(tab,k,fichero,pos,x,y);
	return res;


}

bool backtrack(tablero& tab , int& k , vector<ficha >& fichero,vector<posiciones>& pos, int& x , int& y ){


    bool res = false;
    vector<ficha > copiaFichero = fichero;
//borro todas las que son mas grandes que el tablero
    for( int i = 0; i < copiaFichero.size() ; i++){
        if(copiaFichero[i].base*copiaFichero[i].altura > tab.cantLibres || copiaFichero[i].cantNegras > tab.cantNegras){
            copiaFichero.erase(copiaFichero.begin() + i);
        }
    }

    int newK = copiaFichero.size();


    if(tab.cantLibres == 0){
        return true;
    }else if(newK==0){

        return false;
    }else{
      
        int newx = x;
        int newy = y;

      for(int i = 0;i<newK; i++) {//para todas las fichas
        proximo:
        ficha f1 = copiaFichero[i];//me copio la ficha

        for(int j= 0; j<4;j++){

        posiciones p;

            if(f1.base+x <= tab.base && f1.altura+y <= tab.altura){

                switch(probar(tab,f1,newx,newy)){
                    case 0 : // ultima ficha es solucion

                        f1.rotacion = j;
                        p.id = f1.id;
                        p.fic = f1;
                        p.r = f1.rotacion;
                        p.x = x;
                        p.y = y;
                        pos.push_back(p);
                        actualizar(tab,pos,newx,newy);
                        newK--;
                        return true;

                    case 1 :


                        f1.rotacion = j;
                        p.fic = f1;
                        p.r = f1.rotacion;
                        p.x = x;
                        p.y = y;
                        p.id = f1.id;
                        pos.push_back(p);
                        actualizar(tab,pos,newx,newy);
                        newK--;
                        copiaFichero.erase(copiaFichero.begin()+i);
                        res = backtrack(tab,newK,copiaFichero,pos,newx,newy); //recursion
                        if(res){
                            return true;
                        }else{


                            desactualizar(tab,pos,newx,newy);
                            f1 = pos.back().fic;
                            copiaFichero.insert(copiaFichero.begin()+i,f1);
                            newK ++;
                            pos.pop_back();//saco el ultimo
                            i++;
                            if(i>=newK){
                                return false;
                            }else{
                                goto proximo;
                            }
                        }
                    case 2: //entra la ficha pero puede ser tema de colores
                        rotar(f1);
                        continue;
                    case 3 :// se solapa con otro
                        if (j<2){ // si se solapa con otra con 2 rotaciones ya se q no es
                            rotar(f1);
                        }else{
                            i++;
                            if(i>=newK){
                                return false;
                            }else{
                                goto proximo;
                            }

                        }

                }

            }else{ // capaz no entra
                if(j<2){
                    rotar(f1);
                }else{ //si la rote 2 pruebo con la siguiente
                      break;
                }
            }
        }

        }
        return res;
        }
    }


void actualizar(tablero& tab,vector<posiciones>& pos,int& x,int& y){

    posiciones p = pos.back();

    for(int i = y;i<y+p.fic.altura;i++){
        for(int j = x; j<x + p.fic.base;j++){
            tab.usadas[i][j] = 2;
        }
    }

    tab.cantLibres = tab.cantLibres - p.fic.base*p.fic.altura;
    tab.cantNegras = tab.cantNegras - p.fic.cantNegras;
    int i = x;
    int j = y;
    while(tab.usadas[j][i]!=0 ){
        i++;
        if(i==tab.base){
            i = 0;
            j++;
            if(j==tab.altura){
                break;
            }
        }
    }
    x = i;
    y = j;


}
void desactualizar(tablero& tab,vector<posiciones>& pos,int& x,int& y){

    posiciones p = pos.back();

    for(int i = p.y;i<p.y+p.fic.altura;i++){
        for(int j = p.x; j<p.x + p.fic.base;j++){
            tab.usadas[i][j] = 0;
        }
    }

    tab.cantLibres = tab.cantLibres + p.fic.base*p.fic.altura;
    tab.cantNegras = tab.cantNegras + p.fic.cantNegras;
    x = p.x;
    y = p.y;

}


void rotar(ficha& f1){
	vector<vector<int> > res;
	vector<int> v1;
	int filas = f1.altura;
	int columnas = f1.base;

		for(int i = columnas-1 ; i>=0;i--){
			v1.erase(v1.begin(),v1.end());

			for(int j = 0; j<filas;j++){
				v1.push_back(f1.puntos[j][i]);
			}
			res.push_back(v1);
		}

	f1.puntos = res; //lo copio al del vector

    int newaltura = f1.base;
    f1.base = f1.altura;
    f1.altura = newaltura;


}

int probar(tablero& tab,const ficha& fi, int& x, int& y){

	int cantNegras = 0;
	for(int j = y ; j<fi.altura+y;j++){
		for(int i = x ; i<fi.base+x;i++){
			if(tab.usadas[j][i] == 2){return 3;}//si se choca con alguna otra ficha devuelve 3 que no entra
			if(tab.colores[j][i] == 0){cantNegras++;}// cuento cuantas negras hay en esas posiciones
		}
	}
	if(cantNegras != fi.cantNegras){return 3;} // ya se que no va
	int fix= 0;
	int fiy = 0;
	for(int j = y ; j<fi.altura+y;j++){
        fix = 0;
		for(int i = x ; i<fi.base+x;i++){
			if(tab.colores[j][i] != fi.puntos[fiy][fix] ){
				return 2;
			}//si se choca con alguna otra ficha devuelve 3 que no entra
			fix++;
		}
		fiy++;

	}


	if(tab.cantLibres - fi.base*fi.altura == 0){

		return 0;
	}else{
		return 1;
	}

}

void salida(ostream& out, vector<posiciones >& sol){
	out << sol.size() << endl;     
	for(int i = 0; i<sol.size();i++){
        out << sol[i].id << " " << sol[i].fic.rotacion << " " << sol[i].x << " " << sol[i].y << endl;
    }
}

ostream& operator<<(ostream& os, const posiciones& p){
    os << p.id << ', ' << p.r << ', ' << p.x << ', ' << p.y ;

}
